/*
 * @lc app=leetcode.cn id=862 lang=typescript
 *
 * [862] 和至少为 K 的最短子数组
 */

// @lc code=start
function shortestSubarray(nums: number[], k: number): number {
  const m = nums.length;
  // 前缀和数组
  const sum = new Array(m + 1).fill(0);
  for (let i = 0; i < m; i++) {
    sum[i + 1] = sum[i] + nums[i];
  }

  let pre = -1;
  let ans = -1;
  const deque = [];
  deque.push(0);
  for (let i = 1; i <= m; i++) {
    // 满足结果，我们将队首弹出，继续找距离更短的结果
    while (deque.length && sum[i] - sum[deque[0]] >= k) {
      pre = deque.shift();
    }
    // 更新结果
    if (pre !== -1 && (ans === -1 || i - pre < ans)) {
      ans = i - pre;
    }
    // 单调递增队列
    while (deque.length && sum[i] < sum[deque[deque.length - 1]]) {
      deque.pop();
    }
    deque.push(i);
  }

  return ans;
}
// @lc code=end
